DMS Colloquium: Dr. Gregory Puleo

Speaker: Dr. Gregory Puleo, Auburn University

Title: Edge Coloring of Graphs: Problems and Applications

Abstract: A fundamental result in edge coloring is Vizing's Theorem, which states that every graph can be properly edge-colored using $\Delta(G) + 1$ colors, where $\Delta(G)$ is the maximum degree of $G$. We present two strengthenings of Vizing's Theorem, and discuss some applications to other problems within graph theory.

The first strengthening is a theorem concerning maximal $k$-edge-colorable subgraphs of a graph $G$. Vizing's Theorem is obtained as the special case where $k = \Delta(G)+1$. The second strengthening deals with the core of a graph: the subgraph induced by its vertices of maximum degree. Earlier results, due to Fournier and to Hoffman and Rodger, give sufficient conditions on the core of $G$ which ensure that $G$ is $\Delta(G)$-edge-colorable. We strengthen these results by giving a more general sufficient condition, related to the Fan number parameter recently introduced by Scheide and Stiebitz. This condition is, in a certain sense, best possible. We also discuss multigraph versions of these results.